package com.ycy.leetcode.offer;

import com.ycy.leetcode.tree.TreeNode;

public class Offer07 {

  public static void main(String[] args) {
    Offer07 offer07 = new Offer07();
    int[] preorder = {3, 9, 20, 15, 7};
    int[] inorder = {9, 3, 15, 20, 7};
    offer07.buildTree(preorder, inorder);
    System.out.println();
  }


  public TreeNode buildTree(int[] preorder, int[] inorder) {
    TreeNode root = new TreeNode(preorder[0]);
    int prei = 0;
    int prej = preorder.length - 1;
    int midi = 0;
    int midj = inorder.length - 1;

    build(root, preorder, inorder, prei, prej, midi, midj);
    return root;
  }


  public void build(TreeNode root
          , int[] preorder, int[] inorder
          , int prei, int prej, int midi, int midj) {

    if (root == null) return;
    if (prei >= prej) return;

    int midnew = 0;
    for (int i = midi; i <= midj; i++) {
      //从中序队列中找到root节点
      if (root.val == inorder[i]) {
        midnew = i;
        break;
      }
    }

    // 从前序队列中找出左、右子树 分界下标,这个下标 包含左子树。
    int prenew = prei + (midnew - midi);
    // 如果是 prenew == prenew 说明左子树没有东西

    root.left = prenew == prei ? null : new TreeNode(preorder[prei + 1]);
    root.right = prenew == prej ? null : new TreeNode(preorder[prenew + 1]);
    System.out.println((prei + 1) + " " + prenew + " " + midi + " " + (midnew - 1));
    //前序遍历 不包括根节点，中序遍历 不包括根节点
    build(root.left, preorder, inorder, prei + 1, prenew, midi, midnew - 1);
    build(root.right, preorder, inorder, prenew + 1, prej, midnew + 1, midj);
  }

}
